class BinaryHeap {
    constructor() {
        this.heap = [];
    }


    // 向堆中添加元素
    add(element) {
        this.heap.push(element);
        this.heapifyUp();
    }

    // 从堆中删除最小元素
    removeMin() {
        if (this.heap.length === 0) {
            return null;
        }
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return min;
    }

    // 将堆调整为最小堆
    heapifyUp() {
        let index = this.heap.length - 1;
        let parentIndex = Math.floor((index - 1) / 2);//父节点的位置，向下取整
        //左侧节点位置为2*index+1
        //右侧侧节点位置为2*index+2 
        //父节点位置为index/2
        while (index > 0 && this.heap[index] < this.heap[parentIndex]) {
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
            parentIndex = Math.floor((index - 1) / 2);
        }
    }

    // 将堆调整为最大堆
    heapifyDown() {
        let index = 0;
        let leftChildIndex = 2 * index + 1;
        let rightChildIndex = 2 * index + 2;

        while (leftChildIndex < this.heap.length) {
            let minIndex = index;

            if (this.heap[leftChildIndex] < this.heap[minIndex]) {
                minIndex = leftChildIndex;
            }

            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[minIndex]) {
                minIndex = rightChildIndex;
            }

            if (minIndex === index) {
                break;
            }

            [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
            index = minIndex;
            leftChildIndex = 2 * index + 1;
            rightChildIndex = 2 * index + 2;
        }
    }
}
